package acwing_04;
import java.util.*;
import java.io.*;
public class _875_快速幂 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st;
	static long a,k,p,q;
	public static void main(String[] args) throws IOException {

		int n = Integer.parseInt(br.readLine());

		while(n-- > 0) {
			st = new StringTokenizer(br.readLine());
			a = Integer.parseInt(st.nextToken());
			k = Integer.parseInt(st.nextToken());
			p = Integer.parseInt(st.nextToken());
			q = qmi(a,k,p);
			bw.write(q + "\n");
		}
		bw.flush();
		
	}
	// 计算 a^k %p 的值
	public static long qmi(long a, long k, long p) {
		// 存结果
		long res = 1;
		while(k != 0) {
			// k的二进制末位是1，则 *a %p
			if((k & 1) == 1) {
				res = (res * a) % p;
			}
			// k右移一位 a取平方 模p
			k = k >> 1;
			// 取平方是因为，每次k右移一次，末位的值是前面的值移过来的，需要对应进行a²
			a = a * a % p;
		}
		
		return res;
	}
}
